import java.util.ArrayList;
import java.util.List;

public class MyGraph {

    //图的邻接矩阵
    private int[][] arc;
    //最短路径前驱矩阵
    private int[][] path;
    //最短到顶点的最短路径权值
    private int[][] spt;

    /**
     * 初始化
     *
     * @param arc 邻接矩阵
     */
    public MyGraph(int[][] arc) {
        this.arc = arc;
    }

    public List<Integer> shortestPathFloyd(int from, int to) {
        path = new int[arc.length][arc[0].length];
        for (int i = 0; i < path.length; i++) {
            for (int j = 0; j < path[0].length; j++) {
                path[i][j] = j;
            }
        }
        spt = new int[arc.length][arc[0].length];
        for (int i = 0; i < arc.length; i++) {
            System.arraycopy(arc[i], 0, spt[i], 0, arc[0].length);
        }
        floyd();
        //输出结果
        List<Integer> list = new ArrayList<>();
        list.add(from);
        while (path[from][to] != to) {
            from = path[from][to];
            list.add(from);
        }
        list.add(to);
        return list;
    }

    private void floyd() {
        for (int i = 0; i < spt.length; i++) {
            for (int j = 0; j < spt.length; j++) {
                for (int k = 0; k < spt.length; k++) {
                    if (spt[j][k] > spt[j][i] + spt[i][k]) {
                        spt[j][k] = spt[j][i] + spt[i][k];
                        path[j][k] = path[j][i];
                    }
                }
            }
        }
    }

    public static void main(String[] args) {
        int[][] arc = new int[4][4];
        for (int i = 0; i < arc.length; i++) {
            for (int j = 0; j < arc.length; j++) {
                arc[i][j] = 100000000;
                arc[j][i] = 100000000;
            }
        }
        arc[0][1] = 2;
        arc[0][2] = 8;
        arc[0][3] = 10;
        arc[1][0] = 2;
        arc[1][3] = 10;
        arc[2][0] = 8;
        arc[2][3] = 6;
        arc[3][1] = 10;
        arc[3][2] = 6;
        arc[3][0] = 100;
        MyGraph graph = new MyGraph(arc);
        List<Integer> list = graph.shortestPathFloyd(0, 3);
        System.out.println(list);
    }

}
